package 周赛;

import java.util.Arrays;

public class 数组的最大公因数排序 {

    int[] parent;
    boolean[] isAppear;
    public boolean gcdSort(int[] nums) {
        int n = (int) (1e5 + 10);
        isAppear = new boolean[n];
        parent = new int[n];
        for (int i = 0; i < nums.length; i++) {
            isAppear[nums[i]] = true;
        }
        for (int i = 1; i < parent.length; i++) {
            parent[i] = i;
        }
        for (int i = 1; i < n; i++) {
            if (!isAppear[i]) {
                continue;
            }
            divide(i);
        }
        int[] temp = nums.clone();
        Arrays.sort(temp);
        for (int i = 0; i < temp.length; i++) {
            // System.out.println(temp[i] + " " + nums[i] + " " + find(temp[i]) + " " + find(nums[i]));
            if (find(temp[i]) != find(nums[i])) {
                return false;
            }
        }
        return true;
    }
    //合并两个节点
    public void union(int num1, int num2) {
        // System.out.println(num1 + " " + num2);
        if (find(num1) == find(num2)) {
            return;
        }
        parent[find(num1)] = find(num2);
    }
    //找到头结点
    public int find(int num) {
        if (parent[num] != num) {
            parent[num] = find(parent[num]);
        }
        return parent[num];
    }

    public void divide(int x) {
        int y = x;
        for (int i = 2; i <= x / i; i++) {
            if (x % i == 0) {
                while (x % i == 0) {
                    x /= i;
                    union(y, i);
                }
            }
        }
        if (x != 1) {
            union(y, x);
        }
    }
}
